#define _CRT_SECURE_NO_WARNINGS 1
typedef pair<int, int> PII;
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<PII> st;
        st.push({ heights[0], 0 });
        int ans = 0;
        for (int i = 1; i < heights.size(); i++) {
            auto it = st.top();

            while (!st.empty() && st.top().first > heights[i]) {
                auto t = st.top();
                st.pop();
                int d = i - t.second;
                // ans=max(ans,i-t.second);
                if (!st.empty()) {
                    d += t.second - st.top().second - 1;
                }
                else {
                    d += t.second;
                }
                ans = max(ans, d * t.first);
            }
            st.push({ heights[i], i });
        }
        while (!st.empty()) {
            auto t = st.top();
            st.pop();
            int d = heights.size() - t.second;
            // ans=max(ans,i-t.second);
            if (!st.empty()) {
                d += t.second - st.top().second - 1;
            }
            else {
                d += t.second;
            }
            ans = max(ans, d * t.first);
        }
        return ans;
    }
};